package link;

import java.util.List;

/**
 * 题目描述
 * 给定一个奇数位升序，偶数位降序的链表，将其重新排序。
 *
 * 输入: 1->8->3->6->5->4->7->2->NULL
 * 输出: 1->2->3->4->5->6->7->8->NULL
 * 复制代码
 * 题目分析
 * 按奇偶位置拆分链表，得1->3->5->7->NULL和8->6->4->2->NULL
 * 反转偶链表，得1->3->5->7->NULL和2->4->6->8->NULL
 * 合并两个有序链表，得1->2->3->4->5->6->7->8->NULL
 * 思路很清晰，实现起来有些难度。第2步和第3步分别对应的力扣206. 反转链表和力扣21. 合并两个有序链表，而第1步的解法与力扣328. 奇偶链表差不多。
 */
public class sortOddEvenList {

    public ListNode sortOddEvenList(ListNode head){
        if(head == null || head.next == null){
            return head;
        }

        ListNode[] tmp = partition(head);
        ListNode odd = tmp[0];
        // 反转even;
        ListNode even = tmp[1];
        ListNode evenReverse = reverse(even);
        return merge(odd,evenReverse);
    }


    public ListNode reverse(ListNode head){
        if(head == null){
            return null;
        }
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;

    }

    public ListNode[] partition(ListNode head) {
        ListNode evenHead = head.next;
        ListNode even = evenHead;
        ListNode odd = head;

        while (even != null && even.next != null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        return new ListNode[]{head,evenHead};
    }

    public ListNode merge(ListNode first, ListNode second){
        if(first == null && second == null ) return null;
        if(first == null) return second;
        if(second == null) return first;

        ListNode pre = new ListNode(-1);
        ListNode tmp = pre;
        while (first != null && second != null){
            if(first.val <= second.val){
                tmp.next = first;
                first = first.next;
                tmp = tmp.next;
            }else{
                tmp.next = second;
                second = second.next;
                tmp = tmp.next;
            }

        }
        tmp.next = first == null?second:first;
        return pre.next;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
